#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2018/10/17 17:35
# @Author  : yangdy
# @Email   : yangdy@egu360.com
# @File    : 队列&栈-岛屿的个数.py
# @Software: PyCharm


class Solution:
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        n = len(grid)
        m = len(grid[0])
        steps = []
        for i in [-1, 1]:
            steps.append([0, i])
            steps.append([i, 0])
        state = {}

        def num(x, y):
            return x*m+y

        ans = 0

        def work(x, y):
            que = [(x, y)]
            while len(que) > 0:
                new_que = []
                for q in que:
                    x = q[0]
                    y = q[1]
                    for s in steps:
                        xx = x+s[0]
                        yy = y+s[1]
                        if 0 <= xx < n and 0 <= yy < m:
                            if not state.get((xx, yy)):
                                if grid[xx][yy] == '1':
                                    new_que.append((xx, yy))
                                    state[(xx, yy)] = state[(x, y)]
                que = new_que

        for i in range(n):
            for j in range(m):
                if not state.get((i, j)):
                    if grid[i][j] == '1':
                        ans += 1
                        state[(i, j)] = ans
                        work(i, j)
        return ans


def display(grid, state=None):
    print(state)
    for i in range(len(grid)):
        out = ''
        for j in range(len(grid[0])):
            out += '@' if grid[i][j] == '1' else ' '
            if state is not None and state.get((i,j)):
                out += '(%d)' % state[(i, j)]
        print(out)


def main():
    solve = Solution()
    # grid = [["1", "1", "1", "1", "0"],
    #         ["1", "1", "0", "1", "0"],
    #         ["1", "1", "0", "0", "0"],
    #         ["0", "0", "0", "0", "0"]]
    grid = [["1", "1", "0", "0", "0"],
            ["1", "1", "0", "0", "0"],
            ["0", "0", "1", "0", "0"],
            ["0", "0", "0", "1", "1"]]
    print(grid)
    display(grid)
    print(solve.numIslands(grid))


if __name__ == '__main__':
    main()
